#include <bits/stdc++.h>

using namespace std;

// 随机快速排序，填函数练习风格
// 测试链接 : https://leetcode.cn/problems/sort-an-array/

class Solution 
{
private:
	// 已知arr[l....r]范围上一定有x这个值
	// 划分数组 <=x放左边，>x放右边，并且确保划分完成后<=x区域的最后一个数字是x
    int partition1(vector<int>& nums, int l, int r, int x)
    {
        // a : arr[l....a-1]范围是<=x的区域
        // xi : 记录在<=x的区域上任何一个x的位置，哪一个都可以
        int a = l, xi = 0;
        for(int i = l; i <= r; ++i)
        {
            if(nums[i] <= x)
            {
                swap(nums[a], nums[i]);
                if(nums[a] == x) xi = a;
                ++a;
            }
        }

        swap(nums[a - 1], nums[xi]);
        return a - 1;
    }

    // 随机快速排序经典版(不推荐)
    void quickSort1(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        // 随机这一下，常数时间比较大
		// 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
        int x = nums[rand() % (r - l + 1) + l];
        int mid = partition1(nums, l, r, x);
        quickSort1(nums, l, mid - 1);
        quickSort1(nums, mid + 1, r);
    }

    int first = 0, last = 0;

	// 已知arr[l....r]范围上一定有x这个值
	// 划分数组 <x放左边，==x放中间，>x放右边
	// 把全局变量first, last，更新成==x区域的左右边界
    void partition2(vector<int>& nums, int l, int r, int x)
    {
        first = l, last = r;
        int i = l;
        while(i <= last)
        {
            if(nums[i] == x) ++i;
            else if(nums[i] < x) swap(nums[first++], nums[i++]);
            else swap(nums[last--], nums[i]);
        }
    }

    // 随机快速排序改进版(推荐)
    void quickSort2(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        // 随机这一下，常数时间比较大
		// 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
        int x = nums[rand() % (r - l + 1) + l];
        partition2(nums, l, r, x);
        // 为了防止底层的递归过程覆盖全局变量
		// 这里用临时变量记录first、last
        int left = first, right = last;
        quickSort2(nums, l, left - 1);
        quickSort2(nums, right + 1, r);
    }

public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(nullptr));
        if(nums.size() > 1) quickSort2(nums, 0, nums.size() - 1);
        return nums;
    }
};